1842C - Tenzing and Balls - CodeForces Solution

//Author:  Pranta
//Date:    2023-Jun-24
//Problem: C_Tenzing_and_Balls
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define vout(v) for(int i=0;i<(v).size();i++)cout<<v[i]<<" " 
#define arout(v,n) for(int i=0;i<n;i++)cout<<v[i]<<" " 
#define inp(a,n) ({ fr(i,1,n+1)cin>>a[i]; })
#define fr(i,a,n) for(ll i=a;i<n;++i)
#define rfr(i,a,n) for(int i=n-1;i>=a;--i)
#define mem(a, b) memset(a, (b), sizeof(a))
#define SORT(a) sort(a.begin(),a.end())
#define all(a) (a).begin(),(a).end()
#define pr(a) cout<<a<<endl 
#define sz(a) a.size();
#define ld long double
#define ll long long
#define pb push_back
const ld PI = 3.141592653589793238462;
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX = 2e5 + 5;
using namespace std;
void solve()
{
    ll n;
    cin>>n;
    ll arr[n];
    inp(arr,n);
    vector<vector<ll>>dp(n+1,vector<ll>(2,0));
    vector<ll>pos(n+1,-1);
    fr(i,1,n+1){
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
        if(pos[arr[i]]!=-1){
            ll case1 = max(dp[pos[arr[i]]-1][0],dp[pos[arr[i]]-1][1])+i-pos[arr[i]]+1;
            ll case2 = dp[pos[arr[i]]][1]+i-pos[arr[i]];
            dp[i][1] = max(case1,case2);
        }
        pos[arr[i]]=i;
    }
    cout<<max(dp[n][0],dp[n][1])<<endl;
}
int main()
{
    fast;
    int t;
    cin>>t;
    while(t--)
    solve();
}